class Solution {
public:
    bool CheckCol[9][10];
    bool CheckRow[9][10];
    bool CheckGrid[3][3][10];

    void solveSudoku(vector<vector<char>>& board) {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] != '.')
                {
                    int num = board[i][j] - '0';
                    CheckCol[i][num] = CheckRow[j][num] = CheckGrid[i / 3][j / 3][num] = true;
                }
            }
        }

        dfs(board);
    }

    bool dfs(vector<vector<char>>& board)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                if (board[i][j] == '.')
                {
                    for (int k = 1; k <= 9; k++)
                    {
                        if (!CheckCol[i][k] && !CheckRow[j][k] && !CheckGrid[i / 3][j / 3][k])
                        {
                            board[i][j] = k + '0';
                            CheckCol[i][k] = CheckRow[j][k] = CheckGrid[i / 3][j / 3][k] = true;
                            if (dfs(board)) return true;
                            board[i][j] = '.';
                            CheckCol[i][k] = CheckRow[j][k] = CheckGrid[i / 3][j / 3][k] = false;
                        }
                    }

                    return false;
                }
            }
        }

        return true;;
    }
};